﻿// 0802train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <limits.h>
#include<cmath>
#include <stack>
#include <queue>

using namespace std;

/*
 输入
 2 2 3
 输出
 7

第一个小朋友反馈有两个小朋友和自己同一小区，即此小区有3个小朋友
第二个小朋友反馈有两个小朋友和自己同一小区，即此小区有3个小朋友。
这两个小朋友，可能是同一小区的，且此小区的小朋友只有3个人。
第三个小朋友反馈还有3个小朋友与自己同一小区，则这些小朋友只能是另外一个小区的。这个小区有4个小朋友。
班级里至少有3+4 = 7个小朋友。

输入
50 6 31 43 20 50 40 11 48 48 14 19 34 47 34 47 36 29 7 13 31 35 1 23 47 5 6 48 15 6 16 37 16 41 9 22 29 16 1 6 11 4 44 23 50 26 34 16 31 28 36 37 38 26 24 43 22 25 50 19 34 18 49 36 43 39 12 25 8 1 7 50 5 2 33 44 29 5 14 18 30 42 47 23 17 32 28 10 14 41 24 9 3 48 49 23 50 41 5 34 38 1 26 10 8 26 1 21 2 6 46 42 42 11 12 7 26 13 33 2 31 7 46 29 49 42 19 44 21 42 18 29 40 16 30 5 42 4 9 43 11 5 4 33

输出(1251)
1255

输入
46 2 21 17 38 47 19 32 36 43 28 25 42 25 37 5 15 26 33 35 47 5 23 16 35 50 5 15 2 46 19 43 16 5 19 35 1 28 39 4 41 1 27 23 17 3 15 13 35 13 45 30 32 37 12 26 30 23 5 15 12 49 49 27 5 2 34 16 4 29 9 9 43 37 48 5 50 23 22 12 16 40 20 4 38 46 49 15 17 14 1 16 45 36 29 29 21 45 46 4 21 2 30 2 1 14 5 4 19 38 30 9 4 3 5 35 19 15 3 34 32 10 21 18 24 30 23 18 20 4 47 11 5 27 15 28 50 8 39 14 17 46 21 30 2 18 21 45 26 3 17 45 41 38 38 22 26 9 11 39 17 2 42 35 9 27 49 43 27 50 15 30 5 15 31 3 2 41 23 41 19 47 48 1 10 5 37 29 46 35 18 1 6 50 38 10 9 5 31 12 33 47 25 36 42 4 43 20 26 30 26 4 31 23 17 20 31 26 36 24 4 5 50 41
输出
1303


遗漏情况，反馈人数>小区容纳量

2 2 2 2 3
 */

void solve01(vector<int>&oh_vec)
{
    unordered_map<int, int>oh_map;

    for (int i=0; i<oh_vec.size();i++)
    {
        int curr_num = oh_vec[i];

        if (oh_map.count(curr_num))
        {
            oh_map[curr_num] += 1;
        }
        else
        {
            oh_map[curr_num] = 1;
        }

        //for------
    }

    int result = 0;
    for (auto&map_item:oh_map)
    {
        double people_count = map_item.second;
        double accept_num = map_item.first + 1;

        double curr_total = ceil(people_count / accept_num) * accept_num;
        result += curr_total;
        //for------
    }
    cout << result;
    //solve01
    //------
}



/*
 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

 */

void solve02(int num)
{
    vector<int>oh_dp(num + 1, 0);

    //从2的拆分情况，推导到n的拆分情况
    for (int i=2; i <= num; i++)
    {
        int max_sum = 0;
        for (int j=1; j<i; j++)
        {
            int curr_max_sum = max(j*(i-j), j*oh_dp[i-j]);
            max_sum = max(curr_max_sum, max_sum);
        }
        oh_dp[i] = max_sum;
    }

    cout << oh_dp[num];
    //solve02
    //------
}


/*
一根X米长的树木，伐木工切割成不同长度的木材后进行交易，交易价格为每根木头长度的乘积。
规定切割后的每根木头长度都为正整数，也可以不切割，直接拿整根树木进行交易。
请问伐木工如何尽量少的切割，才能使收益最大化？

输入描述
木材的长度 (X<=50)

输出描述
输出最优收益时的各个树木长度，以空格分割，按升序排列


输入
10
输出
3 3 4
 */
vector<int>GetNewVec(vector<int>&origin_vec, int new_num)
{
    vector<int>oh_vec = origin_vec;
    oh_vec.push_back(new_num);
    return oh_vec;
    //GetNewVec
}

void solve03(int num)
{
    vector<int>oh_dp(num + 1, 0);

    unordered_map<int, vector<int>>oh_map;
    
    for (int i=2; i<=num; i++)
    {
        int curr_max = i;
        vector<int>curr_vec;
        for (int j=1; j<i; j++)
        {
            int origin_sum = j * (i - j);
            int split_sum = j * oh_dp[i - j];

            int split_max = max(origin_sum, split_sum);
            if (split_max >= curr_max) //这里等于也要放进来，相等的时候可以比较段数
            {
                curr_max = split_max;
                if (split_sum > origin_sum)
                {
                    oh_map[i] = GetNewVec(oh_map[i - j], j);
                }
                else
                {
                    //如果split_max==curr_max的时候，选择更小的段数
                    oh_map[i] = { j, i - j };
                }
            }

        }
        if (curr_max==i)
        {
	        //说明分割没有找到大于1*i的组合
            oh_map[i] = { i };
        }

        oh_dp[i] = curr_max;
    }

    vector<int>result_vec = oh_map[num];
    sort(result_vec.begin(), result_vec.end());
    for (auto&item:result_vec)
    {
        cout << item << ' ';
    }

	//solve03
    //------
}



/*
给定一个字符串s，最多只能进行一次变换，
返回变换后能得到的最小字符串（按照字典序进行比较）
变换规则： 交换字符串中任意两个不同位置的字符。

输入描述
一串小写字母组成的字符串s

输出描述
按照要求进行变换得到的最小字符串
 */



int main()
{
	{
        int num = 17;
        //int num;
        //cin >> num;
        solve03(num);
        return 0;
	}
	{
        solve02(10);
		return 0;
	}

    //vector<int>oh_vec = { 2,2,3 };
    vector<int>oh_vec;
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;

    while (oh_sstream>>token)
    {
        oh_vec.push_back(stoi(token));
    }
    

    for (auto&num:oh_vec)
    {
        cout << num << ' ';
    }
    solve01(oh_vec);


    //main------
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
